package leetcode.editor.cn;

import java.util.*;
import leetcode.editor.common.*;

public class ProductOfArrayExceptSelf {

  public static void main(String[] args) {
    Solution solution = new ProductOfArrayExceptSelf().new Solution();
    // put your test code here
    final int[] ints = solution.productExceptSelf(new int[]{1, 2, 3, 4});
    System.out.println(Arrays.toString(ints));
  }
  // leetcode submit region end(Prohibit modification and deletion)

  // leetcode submit region begin(Prohibit modification and deletion)
  class Solution {
    // 维护两个变量，beforeSum表示前缀和，afterSum表示后缀和
    public int[] productExceptSelf(int[] nums) {
      int n = nums.length;
      // 新数组
      int[] ans = new int[n];
      // 额外数组均 填充为 1
      Arrays.fill(ans, 1);
      // 当前元素的前缀和
      int beforeSum = 1;
      // 当前元素的后缀和
      int afterSum = 1;
      for (int j = n - 1; j >= 0; j--) {
        // 结果数组 = 前缀和 * 后缀和
        // 此处 先计算 后缀和
        ans[j] *= afterSum;
        afterSum *= nums[j];
      }
      for (int i = 0; i < n; i++) {
        // 结果数组 = 前缀和 * 后缀和
        // 此处 先计算 前缀和
        ans[i] *= beforeSum;
        beforeSum *= nums[i];
      }
      return ans;
    }
  }
}
